#include<bits/stdc++.h>
#define N 500005
//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
#define gc() getchar()
#define fi first
#define se second
#define Kamisato return
#define Ayaka 0;
#define file(s) freopen(#s".in","r",stdin);freopen(#s".out","w",stdout)
//#define CHECK_MEMORY ___JQH___
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=1e9;
const ll INF=2e18;
bool Memory_Begin;
namespace IO{const int SIZE=(1<<21)+1;char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f,qr;inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf,fflush(stdout);}inline void putc(char x){*oS++=x;if(oS==oT)flush();}template <class I>inline void read(I &x){for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;}template <class I>inline void print(I x){if(!x)putc('0');if(x<0)putc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)putc(qu[qr --]);}inline void reads(string &s){s.clear();for(c=gc();c<33||c>126;)c=gc();for(;c>=33&&c<=126;c=gc())s.push_back(c);}inline void prints(string s){for(char c:s)putc(c);}struct Flusher_ {~Flusher_(){flush();}}io_flusher_;}
using IO::read;using IO::putc;using IO::print;using IO::reads;using IO::prints;
template<class I>I updiv(I x,I y){return (x%y==0?x/y:x/y+1);}
template<class I>bool cmin(I &x,I y){if(x>y)return x=y,1;return 0;}
template<class I>bool cmax(I &x,I y){if(x<y)return x=y,1;return 0;}

mt19937 rnd(time(NULL));
struct Treap
{
	int rt,tot;
	int ls[N],rs[N],sz[N],rd[N];
	ll val[N],sum[N];
	int newnode(ll x){val[++tot]=x;sum[tot]=x,sz[tot]=1;rd[tot]=rnd();return tot;}
	void pushup(int x){sz[x]=sz[ls[x]]+sz[rs[x]]+1;sum[x]=sum[ls[x]]+sum[rs[x]]+val[x];}
	int merge(int x,int y)
	{
		if(!x||!y) return x+y;
		if(rd[x]>rd[y])
		{
			ls[y]=merge(x,ls[y]);
			pushup(y); return y;
		}
		else
		{
			rs[x]=merge(rs[x],y);
			pushup(x); return x;
		}
	}
	pii split(int x,ll k)
	{
		if(!x) return {0,0};
		if(val[x]>k)
		{
			pii y=split(ls[x],k);
			ls[x]=y.se;
			pushup(x);
			return {y.fi,x};
		}
		else
		{
			pii y=split(rs[x],k);
			rs[x]=y.fi;
			pushup(x);
			return {x,y.se};
		}
	}
	void clear(int x){sum[x]=val[x]=ls[x]=rs[x]=sz[x]=rd[x]=0;}
	void modify(ll k)
	{
		pii x=split(rt,k);
		pii y=split(x.fi,k-1);
		if(y.se) clear(y.se),y.se=0;
		else y.se=newnode(k);
		rt=merge(merge(y.fi,y.se),x.se);
	}
	ll getmn(int x,int k)
	{
		if(sz[x]==k) return sum[x];
		if(sz[ls[x]]>=k) return getmn(ls[x],k);
		if(sz[ls[x]]+1>=k) return sum[ls[x]]+val[x];
		return sum[ls[x]]+val[x]+getmn(rs[x],k-sz[ls[x]]-1);
	}
	ll getmx(int x,int k)
	{
		if(sz[x]==k) return sum[x];
		if(sz[rs[x]]>=k) return getmx(rs[x],k);
		if(sz[rs[x]]+1>=k) return sum[rs[x]]+val[x];
		return sum[rs[x]]+val[x]+getmx(ls[x],k-sz[rs[x]]-1);
	}
	int Sz(){return sz[rt];}
}T;

int t;
bool Memory_End;
signed main()
{	
#ifdef CHECK_MEMORY
	cerr<<"Memory: "<<(&Memory_End-&Memory_Begin)/1048576.0<<" MiB\n";
#endif
	file(kte);
	read(t);
	for(ll x;t--;)
	{
		read(x);
		T.modify(x);
		int n=T.Sz();
		int m=(n-1)/2;
		int l=1,r=m,res=0;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(T.getmx(T.rt,mid)<T.getmn(T.rt,mid+1)) res=mid,l=mid+1;
			else r=mid-1;
		}
		ll ans=T.getmx(T.rt,n-1)-T.getmn(T.rt,1);
		for(int i=1;i<=res;i++)
		{
			ll val=T.getmn(T.rt,i+1)-T.getmx(T.rt,i);
			ans-=val;
			if(!(i==m&&n&1)) ans-=val;
		}
		print(max(0ll,ans)),putc('\n');
	}
	Kamisato Ayaka
}
